package com.ls.que76_80;

/**
 * @author ：ls
 * @date ：2021/12/2 9:58
 * @description：...
 */
public class Exist {

    public static boolean search(char[][] board,boolean[][] check, int index_i, int index_j, String word, int k){
//        System.out.println(index_i + " " + index_j + " " + k);
        if (board[index_i][index_j] != word.charAt(k))
            return false;
        if (k == word.length() - 1){
//            System.out.println("找到了");
            return true;
        }

        check[index_i][index_j] = true;
        int[][] change = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        int now_i=0, now_j=0;
        boolean flag = false;
        int h = board.length;
        int w = board[0].length;
        for (int i=0; i< 4; i++){
            now_i = index_i + change[i][1];
            now_j = index_j + change[i][0];
            if (now_i < 0 || now_i > h-1 || now_j < 0 || now_j > w-1 || check[now_i][now_j])
                continue;

            flag = search(board,check, now_i, now_j, word, k+1);
            if (flag)
                return true;
        }
        check[index_i][index_j] = false;
        return false;


    }

    public static boolean exist(char[][] board, String word) {
        boolean flag = false;
        boolean[][] check = new boolean[board.length][board[0].length];
        for (int i=0; i< board.length; i++){
            for (int j=0; j< board[0].length; j++){
                flag = search(board, check, i, j,word, 0);
                if (flag)
                    break;
            }
            if (flag)
                break;
        }
        return flag;
    }


    public static void main(String[] args) {
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "ABCCED";
        System.out.println(exist(board, word));
    }
}
